package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * [322]零钱兑换.java
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * <p>
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * <p>
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 示例 1：
 * <p>
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * <p>
 * 示例 2：
 * <p>
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * <p>
 * 示例 3：
 * <p>
 * 输入：coins = [1], amount = 0
 * 输出：0
 * <p>
 * 提示：
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 2³¹ - 1
 * 0 <= amount <= 10⁴
 * <p>
 * Related Topics 广度优先搜索 数组 动态规划 👍 2158 👎 0
 */
public class Lc322 {


    public static void main(String[] args) {
        int[] nums = {1,2,5};
//        int[] nums = {2};
        System.out.println(coinChange1(nums, 11));

    }

    public static int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        //此处必须安排 {比小模式} + {默认大数字}
        // 不能        {比大模式} + {默认 -1 }
        // 因为例如 {1,2,5}组合10来说,coin=1完毕dp={0，1，2，3，4，5，6，。。。10},
        // 而coin=5时不能取代dp[10]=10为dp[10]=2
        // 之所以Integer.MAX_VALUE - 1,因为Integer.MAX_VALUE 如果+1会变负数
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for (int coin : coins) {
            // 从面额开始,防止 i-coin为负数越界
            for (int i = coin; i <= amount; i++) {
                int cur = dp[i];
                int last = dp[i - coin];
                dp[i] = Math.min(cur, last + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
    }


}
